1. Field of the Invention
The present invention relates to an image synthesis method, an image synthesizer, and a recording medium on which an image synthesis program has been recorded.
2. Description of the Prior Art
A technique for calculating an optical flow from two images, and registering the two images on the basis of the obtained optical flow has been known. Description is made of a conventional method of calculating an optical flow.
(1) Lucas-Kanade Method
A large number of methods of calculating the apparent optical flow of a moving object in a moving image have been conventionally proposed. The Lucas-Kanade method which is a local gradient method out of the methods is one of the best methods. The reason for this is that the speed of processing is high, implementing is easy, and the result has confidence.
As for the details of the Lucas-Kanade method, see an article: B. Lucas and T. Kanade, xe2x80x9cAn Iterative Image Registration Technique with an Application to Stereo Vision,xe2x80x9d In Seventh International Joint Conference on Artificial Intelligence (IJCAI-81), pp.674-979, 1981.
The outline of the Lucas-Kanade method will be described.
When a gray scale pattern I=(x, y, t) of image coordinates p=(x, y) at time t is moved to coordinates (x+xcex4x, y+xcex4y) with its gradation distribution kept constant after a very short time period (xcex4t), the following optical flow constraint equation (1) holds:                                                                         ∂                I                                            ∂                                  xe2x80x83                                ⁢                x                                      ⁢                          xe2x80x83                        ⁢                                          δ                ⁢                                  xe2x80x83                                ⁢                x                                            δ                ⁢                                  xe2x80x83                                ⁢                t                                              +                                                    ∂                I                                            ∂                y                                      ⁢                          xe2x80x83                        ⁢                          δy                              δ                ⁢                                  xe2x80x83                                ⁢                t                                              +                                    ∂              I                                      ∂              t                                      =        0                            (        1        )            
In order to calculate an optical flow {v=(xcex4x/xcex4t, xcex4y/xcex4t)=(u, v)} in a two-dimensional image, another constraint equation is required because the number of unknown parameters is two. Lucas and Kanade have assumed that the optical flow is constant in a local region of an object.
Suppose the optical flow is constant within a local region xcfx89 on an image, for example. In this case, a squared error E of a gray scale pattern which is to be minimized can be defined by the following equation (2) when the following substitutions are made:                                                                         I                0                            ⁡                              (                P                )                                      =                          I              ⁢                              (                                  x                  ,                  y                  ,                  t                                )                                              ,                      
                    ⁢                                                    I                1                            ⁡                              (                                  p                  +                  v                                )                                      =                          I              ⁡                              (                                                      x                    +                    u                                    ,                                      y                    +                    v                                    ,                                      t                    +                                          δ                      ⁢                                              xe2x80x83                                            ⁢                      t                                                                      )                                                    ⁢                  
                ⁢                  E          =                                    ∑              ω                        ⁢                          xe2x80x83                        ⁢                                          [                                                                            I                      1                                        ⁡                                          (                                              p                        +                        v                                            )                                                        -                                                            I                      0                                        ⁡                                          (                      p                      )                                                                      ]                            2                                                          (        2        )            
When v is very small, the terms of second and higher degrees in Taylor""s expansion can be ignored, so that a relationship expressed by the following equation (3) holds:
I1(p+v)=I1(p)+g(p)vxe2x80x83xe2x80x83(3)
where g(p) is a linear differential of I1(p).
The error E is minimized when the derivative of E with respect to v is zero, so that a relationship expressed by the following equation (4) holds:                                                         0              =                              xe2x80x83                            ⁢                                                ∂                                      ∂                    v                                                  ⁢                E                                                                                        ≈                              xe2x80x83                            ⁢                                                ∂                                      ∂                    v                                                  ⁢                                                      ∑                    ω                                    ⁢                                      xe2x80x83                                    ⁢                                                            [                                                                                                    I                            1                                                    ⁡                                                      (                            p                            )                                                                          +                                                                              g                            ⁡                                                          (                              p                              )                                                                                ⁢                          v                                                -                                                                              I                            0                                                    ⁡                                                      (                            p                            )                                                                                              ]                                        2                                                                                                                          =                              xe2x80x83                            ⁢                                                ∑                  ω                                ⁢                                  xe2x80x83                                ⁢                                  2                  ⁢                                                            g                      ⁡                                              (                        p                        )                                                              ⁡                                          [                                                                                                    I                            1                                                    ⁡                                                      (                            p                            )                                                                          +                                                                              g                            ⁡                                                          (                              p                              )                                                                                ⁢                          v                                                -                                                                              I                            0                                                    ⁡                                                      (                            p                            )                                                                                              ]                                                                                                                              (        4        )            
Therefore, the optical flow v is found by the following equation (5):                     v        ≈                                            ∑              ω                        ⁢                          xe2x80x83                        ⁢                                          g                ⁡                                  (                  p                  )                                            ⁡                              [                                                                            I                      0                                        ⁡                                          (                      p                      )                                                        -                                                            I                      1                                        ⁡                                          (                      p                      )                                                                      ]                                                                        ∑              ω                        ⁢                          xe2x80x83                        ⁢                                          g                ⁡                                  (                  p                  )                                            2                                                          (        5        )            
Furthermore, the optical flow can be found with high precision by Newton-Raphson iteration, as expressed by the following equation (6):                                           v                          k              +              1                                =                                    v              k                        +                                          ∑                                  xe2x80x83                                ⁢                                                      g                    k                                    ⁡                                      [                                                                  I                        0                                            -                                              I                        1                        k                                                              ]                                                                              ∑                                  xe2x80x83                                ⁢                                                      (                                          g                      k                                        )                                    2                                                                    ⁢                  
                ⁢                                            I              1              k                        =                                          I                1                            ⁡                              (                                  p                  +                                      v                    k                                                  )                                              ,                      
                    ⁢                                    g              k                        =                          g              ⁡                              (                                  p                  +                                      v                    k                                                  )                                              ,                      
                    ⁢                                    I              0                        =                                          I                0                            ⁡                              (                p                )                                                                        (        6        )            
(2) Hierarchical Estimation Method
The largest problem of the gradient methods, including the Lucas-Kanade method, is that they cannot be applied to a large motion because a good initial value is required. Therefore, a method of producing images respectively having resolutions which differ at several levels like a pyramid hierarchical structure to solve the problem has been conventionally proposed.
Images having resolutions which differ at several levels are first previously produced from each of two consecutive images. An approximate optical flow is then calculated between the images having the lowest resolution. A more precise optical flow is calculated between the images having resolutions which are higher by one level. The processing is successively repeated until the optical flow is calculated between the images having the highest resolution.
FIG. 4, FIG. 3, FIG. 2, and FIG. 1 respectively illustrate an original image, an image having a lower resolution than that of the original image shown in FIG. 4, an image having a lower resolution than that of the image having a low resolution shown in FIG. 3, and an image having a lower resolution than that of the image having a low resolution shown in FIG. 2. In FIGS. 1 to 4, S indicates one patch.
An optical flow is gradually found from the image shown in FIG. 1 (an image in a hierarchy 1) the image shown in FIG. 2 (an a hierarchy 2 the image shown in FIG. 3 (an image in a hierarchy 3), and the image shown in FIG. 4 (an image in a hierarchy 4) in this order. In FIGS. 1 to 4, an arrow indicates an optical flow vector found for each patch.
However, the problem is that in a real image, there are few regions containing sufficient texture, so that a reliable optical flow is not obtained.
A technique for affixing a plurality of images to one another and synthesizing the images to obtain a seamless image having a wide field of view and having a high resolution (image mosaicking) has been conventionally actively studied. Classical applications include synthesis of aerial photographs or satellite photographs. In recent years, a method of synthesizing a plurality of digital images to obtain a seamless panoramic image, and constructing a virtual reality environment has been paid attention to.
The following two methods have been known as a technique for obtaining a panoramic image by synthesis.
The first method is a method of first translating a camera to previously pick up a plurality of images. The plurality of images obtained are simultaneously displayed on a monitor by a personal computer. A user designates corresponding points between the two images, to synthesize the two images.
In the first method, the motion of the camera is restricted to translation. In the first method, the user must designate the corresponding points.
The second method is a method of fixing a camera to a tripod and restricting the motion of the camera to only rotation on a horizontal surface, to pick up a plurality of images. The plurality of images obtained are projected on a cylindrical surface, to synthesize the images (see U.S. Pat. No. 5,396,583).
In the second method, the, motion of the camera must be restricted to only rotation on a horizontal surface. Further, the focal length or the angle of view of the camera must be measured.
An object of the present invention is to provide an image synthesis method in which highly precise positioning is performed even when a scene having a large depth is obtained by synthesis, an image synthesizer,and a recording medium on which an image synthesis program has been recorded.
Another object of the present invention is to provide an image synthesis method in which a seamless panoramic image can be obtained from a plurality of images, a camera for picking up the plurality of images is allowed to freely move, and the focal length need not be measured, an image synthesizer, and a recording medium on which an image synthesis program has been recorded.
A first image synthesis method according to the present invention is an image synthesis method for synthesizing a first image and a second image without a seam on the basis of coordinate values, on the first image, respectively corresponding to a plurality of feature points which are set in a portion, which is overlapped with the second image, of the first image and coordinate values, on the second image, at positions, on the second image, respectively corresponding to the feature points, characterized by comprising the first step of dividing both the images for each triangular patch having the three adjacent feature points as vertexes, and finding a transform equation for finding a position, on the first image, corresponding to a point on the second image for the triangular patch; the second step of finding the coordinate value, on the first image, corresponding to each of pixels in each of the triangular patches, on the second image using the transform equation calculated for the triangular patch; the third step of synthesizing the first image and the second image using t he coordinate value, on the first image, corresponding to each of the pixels on the second image, which is found at the second step.
An example of the transform equation found for each triangular patch is a planar projective transform matrix. The planar projective transform matrix is found on the basis of corresponding points at the three vertexes of the triangular patch and a fundamental matrix representing epipolar constraint conditions between the first image and the second image, for example. The planar projective transform matrix may be found on the basis of a correspondence between corresponding points at the three vertexes of the triangular patch and epipoles representing epipolar constraint conditions between the first image and the second image.
An example of the transform equation found for each triangular patch is an affine transform matrix. The affine transform matrix is found on the basis of the corresponding points at the three vertexes of the triangular patch.
An image synthesizer according to the present invention is an image synthesizer for synthesizing a first image and a second image without a seam on the basis of coordinate values, on the first image, respectively corresponding to a plurality of feature points which are set in a portion, which is overlapped with the second image, of the first image and coordinate values, on the second image, at positions, on the second image, respectively corresponding to the feature points, characterized by comprising first means for dividing both the images for each triangular patch having three adjacent feature points as vertexes, and finding a transform equation for finding a position, on the first image, corresponding to a point on the second image for the triangular patch; second means for finding the coordinate value, on the first image, corresponding to each of pixels in each of the triangular patches, on the second image using the transform equation calculated for the triangular patch; third means for synthesizing the first image and the second image using the coordinate value, on the first image, corresponding to each of the pixels on the second image which is found by the second means.
A computer readable recording medium on which an image synthesis program has been recorded according to the present invention is a computer readable recording medium on which an image synthesis program for synthesizing a first image and a second image without a seam on the basis of coordinate values, on the first image, respectively corresponding to a plurality of feature points which are set in a portion, which is overlapped with the second image, of the first image and coordinate values, on the second image, at positions, on the second image, respectively corresponding to the feature points has been recorded, characterized by comprising the first step of dividing both the images for each triangular patch having three adjacent feature points as vertexes, and finding a transform equation for finding a position, on the first image, corresponding to a point on the second image for the triangular patch; the second step of finding the coordinate value, on the first image, corresponding to each of pixels in each of the triangular patches, on the second image using the transform equation calculated for the triangular patch; and the third step of synthesizing the first image and the second image using the coordinate value, on the first image, corresponding to each of the pixels on the second image found at the second step.
A second image synthesis method according to the present invention is an image synthesis method for synthesizing a first image and a second image, characterized by comprising the first step of extracting from the first image a plurality of partial images which are effective for tracking by an optical flow between the first image and the second image as feature points; the second step of tracking a point, on the second image, corresponding to each of the feature points on the first image on the basis of the optical flow between both the images; the third step of finding a coordinate value, on the first image, corresponding to each of pixels on the second image on the basis of each of the feature points on the first image and the corresponding points on the second image which is found at the second step; and the fourth step of synthesizing the first image and the second image on the basis of the coordinate value, on the first image, corresponding to each of the pixels on the second image which is obtained at the third step, the third step comprising the step of dividing both the images for each triangular patch having three adjacent feature points as vertexes, and finding a transform equation for finding a position, on the first image, corresponding to the point on the second image for the triangular patch, and the step of finding the coordinate value, on the first image, corresponding to each of the pixels in the triangular patch on the second image using the transform equation calculated for the triangular patch.
An example of the first step is one comprising the steps of extracting an overlapped portion between the first image and the second image, and extracting from the portion, which is overlapped with the second image, of the first image a plurality of partial images which are effective for tracking by the optical flow between both the images as feature points.
At the step of extracting the overlapped portion between the first image and the second image, the overlapped portion between the first image and the second image is extracted on the basis of either one of the SSD method and the normalized cross-correlation method.
An example of the second step is one comprising the step of finding the optical flow from the first image and the second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating the optical flow having low confidence out of the optical flows obtained in the respective stages of the optical flow estimation method using the optical flows in its surrounding regions, and the step of tracking the point, on the second image, corresponding to each of the feature points on the first image on the basis of the obtained optical flow.
The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.